package leetcode.D400.T310;

import java.util.*;

class Solution {
    /*// 解法一：回溯+剪枝，超时！
    private int minHeight = Integer.MAX_VALUE;
    private int num;
    private int maxHeight;
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<n; ++i) {
            map.put(i, new LinkedList<>());
        }
        for(int i=0; i<edges.length; ++i) {
            int a = edges[i][0], b = edges[i][1];
            map.get(a).add(b);
            map.get(b).add(a);
        }
        boolean[] used = new boolean[n];
        for(int i=0; i<n; ++i) {
            used[i] = true;
            num = 1;
            maxHeight = 1;
            dfs(n, map, used, i, i, 1, result);
            used[i] = false;
        }
        return result;
    }
    private void dfs(int n, Map<Integer, List<Integer>> map, boolean[] used, int root, int cur, int height, List<Integer> result) {
        maxHeight = Math.max(maxHeight, height);
        if(num == n) {
            if(maxHeight < minHeight) {
                minHeight = maxHeight;
                result.clear();
                result.add(root);
            } else if(maxHeight == minHeight) {
                result.add(root);
            }
        }
        if(height > minHeight) {
            return;
        }
        List<Integer> neighbors = map.get(cur);
        for (int neighbor : neighbors) {
            if(used[neighbor]) {
                continue;
            }
            used[neighbor] = true;
            num++;
            dfs(n, map, used, root, neighbor, height+1, result);
            used[neighbor] = false;
        }
    }*/
    /*// 解法2：回溯+剪枝+哈希记录
    private int minHeight = Integer.MAX_VALUE;
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new LinkedList<>();
        Map<Integer, Map<Integer, Integer>> heightMap = new HashMap<>();
        Map<Integer, List<Integer>> edgeMap = new HashMap<>();
        for(int i=0; i<n; ++i) {
            heightMap.put(i, new HashMap<Integer, Integer>());
            edgeMap.put(i, new LinkedList<Integer>());
        }
        for(int j=0; j<edges.length; ++j) {
            int a = edges[j][0], b = edges[j][1];
            edgeMap.get(a).add(b);
            edgeMap.get(b).add(a);
        }
        boolean[] used = new boolean[n];
        for(int i=0; i<n; ++i) {
            Arrays.fill(used, false);
            used[i] = true;
            int height = dfs(i, edgeMap, heightMap, used);
            if(height < minHeight) {
                minHeight = height;
                result.clear();
                result.add(i);
            } else if (height == minHeight) {
                result.add(i);
            }
        }
        return result;
    }
    private int dfs(int root, Map<Integer, List<Integer>> edgeMap, Map<Integer, Map<Integer, Integer>> heightMap, boolean[] used) {
        List<Integer> neighbors = edgeMap.get(root);
        int curHeight = 0;
        for (Integer neighbor : neighbors) {
            if(used[neighbor]) {
                continue;
            }
            Map<Integer, Integer> temp = heightMap.get(neighbor);
            int height = 0;
            if(temp.containsKey(root)) {
                height = temp.get(root);
            } else {
                used[neighbor] = true;
                height = dfs(neighbor, edgeMap, heightMap, used);
                temp.put(root, height);
            }
            curHeight = Math.max(curHeight, height);
        }
        return curHeight + 1;
    }*/
    // 解法3：bfs
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new LinkedList<>();
        if(n == 1) {
            result.add(0);
            return result;
        }
        int[] degree = new int[n];
        List<List<Integer>> edgeMap = new ArrayList<>(n);
        for(int i=0; i<n; ++i) {
            edgeMap.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
            edgeMap.get(edge[0]).add(edge[1]);
            edgeMap.get(edge[1]).add(edge[0]);
        }
        Deque<Integer> dq = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if(degree[i] == 1) {
                dq.addLast(i);
            }
        }
        while(!dq.isEmpty()) {
            int size = dq.size();
            result = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                int front = dq.removeFirst();
                result.add(front);
                List<Integer> neighbors = edgeMap.get(front);
                for (Integer neighbor : neighbors) {
                    degree[neighbor]--;
                    if(degree[neighbor] == 1) {
                        dq.addLast(neighbor);
                    }
                }
            }
        }
        return result;
    }
}
